1939
25 623
535024569 634768728 850930649 969961620 365281027 582803450 199172924 5671978 177734759 916944794 438764485 647504827 999580094 224744537 75532769 618349895 644303144 853267002 786940544 830997237 697534857 482780070 231095706 758355343 256849159 454350825 655932581 535697668 883100558 721866674 496080161 441131238 976286028 918594455 737865485 715970794 557318965 114474127 713426286 391161194 986465152 948746358 356830927 649556454 855551527 992398476 367421884 429326718 290418539 775557622 710469958 422293882 921600591 816439356 183751554 460889027 379969304 320899529 704502794 104260967 836535763 77458031 555457658 353578264 282845903 951957984 116181236 667711406 37894430 268757046 45542045 789177505 669249817 438486124 82342429 76512911 627804377 436723938 368186915 877021628 219851967 611422173 218041311 338116749 287108076 19145220 585591686 636899340 894103753 497534692 134607570 20951655 672504705 836365165 384302975 708624753 634350210 290441332 686586319 437718816 265961216 95945007 848347399 420486669 995507058 239949244 537426416 800155127 195176467 240733082 546348887 337001536 46263138 335301677 46507661 438174830 354707106 577554750 239980007 812293292 930647643 755206009 687699775 674267206 185013975 682745070 355403377 189551664 810725030 532086673 770960863 979374464 583993626 11013562 198452974 850192368 919413452 727025318 327086727 215641693 630334485 466755316 738268567 202750794 310747542 331129128 199759759 80656222 136769713 511647275 872617700 260379617 705112077 416085961 450268048 144602947 916887062 148540722 214751631 665630102 341592442 788192121 403198307 822404879 804924333 742608920 383432337 108480137 873723750 96752490 300429858 611755009 21494048 985466672 529846563 180326171 886302618 943712525 728165157 458515356 570602071 406424842 623889597 378550254 472428063 474485266 151593989 269739935 124449148 761853047 931304217 953059810 712038718 468656747 445035163 130017804 766830840 864438920 81259568 384726552 928291712 872431689 92309249 800582436 72981363 29055119 262803003 798764018 827004334 915638812 157306767 873382760 114554326 728923163 831658931 127958288 431036113 714755734 606114526 615435672 683466059 53101311 557283664 446014803 198368306 861849256 700993480 495716023 750548283 830739274 658476556 142217949 808504667 442892162 58465637 32507909 278272846 866396495 936403232 90699791 702564371 782888598 63451918 453297922 155842413 439302558 838162948 35398025 534472292 573389716 950307932 212806000 728116674 453616905 938737779 848962092 943710871 409852527 945338665 434599761 852980406 262405279 363806308 762551577 158358325 124795221 348360077 975087332 844143857 730133938 244482577 725848498 851546887 287639226 137414625 689953963 787146076 633571284 116595698 302751639 308979479 250897741 401730750 967600998 857924386 842030293 150713538 621812906 172208300 943656960 976150782 609827864 534873513 340690118 415705976 415095051 590523728 506967555 625181113 274327041 139093660 41118200 351529806 803709724 602333900 199007944 523803208 817161377 444007908 674702076 434729404 644063100 619904298 678461951 294327364 672972219 825550249 347348643 837533821 527234319 261609137 999075227 217153927 60585294 25759829 815557631 787421064 105427699 973522923 22805451 722587177 733010332 213453968 546988639 753742615 395607179 755031970 934343936 770403459 524061991 460891972 854937430 125215139 495019896 601393885 951894508 548524847 314194606 554198425 601881780 163477988 111064474 536846054 340877696 277369093 811496242 50094329 898317962 108644053 422170386 261256519 664890605 11000606 6655990 942302476 326074153 927075245 797167169 398397383 291099555 503063763 806922874 479892924 451590946 635168742 314319305 80511089 335948627 516129214 160380542 621439281 192112967 207285560 884747915 401376140 79256048 303165366 106616837 297588181 24721063 610855838 438696359 115816867 191630761 219156183 996977998 479294032 865102997 622460239 982373502 146483581 558021872 399179127 778753755 735928204 275760801 820572357 354464945 747671589 908891253 619745329 255096174 830398129 422612636 173778104 495720482 212717794 568760106 711756765 623845894 49310505 778337431 278762531 329799922 636980543 357382207 418949524 798509540 851197085 559647459 333367869 853652352 474704643 82217767 248540847 800117899 825804533 312040466 626021504 957107823 376789049 13030800 784595144 377914299 98505818 7649523 52585124 339492000 552989992 709768558 219666359 134046069 393724726 32971929 400634532 804596019 759963227 684924144 898818965 171009529 121895474 815934548 955904183 237041033 252956313 515025544 100664508 598779849 43118133 846622645 710245207 779097412 238846189 218357990 491015619 49650087 443890795 419013773 109670205 745094212 98423967 803123964 980263301 965232786 46835259 886588653 764932450 862387882 179844407 573570555 408297243 761471948 575353166 306031399 642334974 112690904 251004544 398661971 631151068 351695574 136777103 778904010 474160011 333081966 143677058 317819062 741984611 419486064 975052068 438429097 927502530 862548814 101404037 785326101 956902280 976244637 938506360 283699156 545396379 40559512 263941652 343398304 225438308 202618269 685571124 430013340 951083345 454267821 661062391 418119113 85044817 183093232 647407936 927952018 197377883 387403567 548026678 451243841 195452903 84313433 166193349 199864455 779978611 722673150 69565980 948486904 61966847 441541847 453218350 588929932 273500817 205707324 897288497 738361376 706880435 418372524 339334945 206273011 399261168 769485385 548951614 96884265 236141658 482684761 69918089 504396876 871328007 648910022 886275403 525747397 522353551 242204575 882160015 201719655 392689552 215545493 942326435 502123493 724053802 744972415 360174491 49123415 422551428 521628374 714076878 93148602 400462149 772061754 697098839 978947692 733789979 590311147 166065301 59380916 216755256 47908176 384834731 627512632 760893135 16119412 710130945 879884676 198777500 450883204 939083713 474779274 28900698 909570386 520203099 645938973 851047242 548993749 180586753 817641077 514820018 734870439 653305644 264438958 780292444 894041989 474479125 592651592 538159379 362694099 556297788 476910504 607186473 87589909 25935077 26686358 856085748 511810167 123906710 728153021 653368652 415433287 208266139 139143727 653859087 344493173 1701506 792346334 923972766 173889561 901762207 691849764 2114909 238236397 885598857 116827452 918556214 153485775 283112603 264709318 458358807 71450945 612822900 148717895 109721199 904413673 866839672 803758503 255321525 422593809 358380108 720592817 625333217 893499688 698974557 57563798 616732913 611850303 262273114 585022314 650041190 107147916 743910070 485731750 71923396 341271274 243212071 837032356 131712534 360365912 653334058 765913382 45857383 101373814 773895804 504729040 768260937 952809739 468546978 418915241 632158546 430956161 246741090 883833758 536005787 686967143 25076552 505963519 698314560 441888494 721433378 551078656 939898338 346526829 940505476 748676410 718395432 263857630 997726533 882607143 962330425 438819422 433780480 551573673 252276803 300801712 966039445 595619203 837252856 386743739 345930917 873638367 997003788 799131912 193452825 517839302 477463480 937644357 763220891 383570603 579952186 358886596 166465307 148235745 562175059 906419708 494552395 528573728 772657095 771578887 734146852 880057092 528813536 512970531 464874335 807594894 773433836 323589938 49180925 230230689 942574523 33252921 110721472 421212294 375353889 661433060 75328687 578650728 714253178 377758977 706464406 202507481 509807137 854553088 254661251 793920588 144837879 458900858 913758283 768525208 569754083 718579111 109013251 802241147 98676812 385362406 548780423 877999637 362637729 442016057 425087734 757152105 133345745 254784198 936566067 204928479 268509139 14078551 54624614 905362885 101653024 661792987 324881529 662798025 637105460 726229731 612411804 962148481 745386000 551148838 862243010 656859363 558355643 779329789 315052834 773984973 427727036 333838055 450995126 134149246 681201570 669097222 727763391 855335451 309160829 336695713 648670527 773660203 337839458 466408864 930851709 867090459 691953642 922489107 225286533 742880956 363846067 251795372 476646565 506081984 521970654 257036095 329879794 448971072 388307599 330758729 928163777 922883129 613243761 618591847 537678382 41909514 540943407 61395674 135410072 701639927 141739260 161306890 28573219 329583529 649477900 160806656 999057717 275394476 633581337 891184618 357545977 917890800 998120415 777647770 334149599 136358217 408146079 688013320 379520282 850475759 800240544 908631500 297638688 379844351 738671273 814758052 545540398 847989751 808924553 21824244 677872322 486063678 46903440 380266817 418405407 254296218 548999955 354586293 181100236 810709175 916578283 229646751 468275733 802448295 337523190 357899760 898637705 58197085 729761941 855313342 506748794 665204785 6583853 305700804 133445504 105792863 421288102 509875680 49848566 875798407 82610671 36618133 97864059 555186735 146899576 891546759 75373427 426447676 11558326 854533889 753767044 745242493 507947170 195151986 617183769 286981920 795802170 788577771 559662562 985436219 549483007 426982051 256946258 329609028 603768438 76908659 621065504 740964249 591579047 455101531 329830343 176518138 691632545 468039931 272004101 131372810 945901812 178739995 910699104 422145489 205644597 738883107 525238428 464919100 420718461 837641379 170993734 865969052 706364651 35316429 259653933 281095459 358109469 553930998 809215459 833127018 186449595 973173273 793641024 988402670 927312877 264181331 485360607 766215566 789037791 553180008 69030560 116055823 374292548 798598461 871215396 188423832 734151120 246222428 654204756 891288374 569390781 239671411 445429979 220474201 275083335 743899861 487567271 912665941 314542640 996363511 898956396 549062115 745090365 752102644 887553825 201428125 486183862 408894474 273744768 835218565 573591018 939351835 855189386 225032319 117365929 378050861 916034561 108969938 22163400 353753066 449402093 463240874 541018273 258314785 48335384 659981977 612936336 397089859 286088082 582130450 887397239 896487654 882653229 15751661 525443642 395760966 443706369 512836582 525854020 848116159 339997930 21377310 481060609 598539348 277133573 435909528 370666082 38474540 228818743 146403773 909341532 199778575 305334182 30740185 17991017 365589997 591565373 685353371 673750021 925202263 21108525 606824601 849707826 719047940 889139558 210648266 120624117 851473230 207845666 43046922 767199446 533362610 235003483 869219737 810559076 279326548 752248656 43563676 533566895 796753784 740080900 413586075 266402508 247997450 306875839 304463361 700371797 409944087 694836619 655717024 177766118 604119122 442271416 238983210 380314529 453685648 749705304 897322681 991321259 225490764 673542340 118173000 892271789 432855588 635248149 738336311 520827475 159516250 767058603 443225547 984192208 496020563 678724522 571082411 402494553 789826843 412647800 50525284 153804965 116525792 477081665 151974375 398135156 809582963 958915699 776178694 393319685 976080074 44808002 405126650 42364573 778092929 306101541 189228512 244723463 411869012 350436439 41996087 3306255 808160166 557077335 325137763 253857286 555019773 489346920 78515757 943508033 952926851 867700498 240013890 131374490 564245127 250267295 757282735 915158509 754921722 685557407 117088875 705750940 825180403 134214756 470614222 747934220 487535147 40352903 688954386 172000806 211604354 698994017 166075609 851306199 314520440 450403731 416970150 620613520 679197876 489220222 916504930 767625926 29680257 611059916 218726361 492309107 616137548 706125029 927029307 387718803 396592423 771174779 755330971 660478888 729153097 338393599 776464243 593446199 349774732 775427881 167044126 485028937 715501806 355394932 488022877 198913003 803883024 148051871 590492371 554556334 551322298 440919341 608439945 933342759 954528085 525998822 257112939 927880560 735692655 504528212 283933640 677804454 46263867 451601735 892025302 269779305 102709518 727915089 404543531 155573855 162958307 362449227 541973573 331593648 162211800 330662606 528995076 116244107 692161455 556558267 302996778 176689824 161124430 322894772 602264034 991941797 193764159 590891936 124053302 355564242 646795569 325542443 217155224 256176484 671362677 158273603 573347162 818668829 933410690 156606876 843640629 183775682 731631473 618446637 375425222 470131868 622520449 475021745 555225612 331305208 371035284 143627303 782917868 309232295 356720049 413088339 167494061 679292543 477167744 337976123 997157757 490056407 937047761 533117866 333164266 747502607 522219029 794791600 523186281 336573190 773413347 869579807 902302418 955702178 686490229 764781840 164788193 838489420 91197736 107079773 873879735 926239601 58513664 776763684 717401688 638007298 513521441 825409866 901757483 367526901 271707479 288628725 992241789 491731905 861426319 540801553 445332734 151016934 187353436 382263501 961630530 462491491 200646259 401702427 243237697 688954942 28747055 596832563 572393431 153423872 295041549 188372752 98784069 885340726 973086001 717673201 383698350 114068721 811159776 71202010 677520795 693571911 15123972 498606097 562639480 38724048 294799019 862281633 493616404 985245481 431236744 304235738 791338533 341792884 196520817 521264591 179549378 711486422 89081311 10402262 583333607 627599096 114957169 911876620 542685684 533991815 665147241 65892815 600066350 661724597 313081645 482125122 69679677 390146229 189225159 201810892 689408940 320057666 327094630 735915673 954755437 874429465 709350363 197293335 361796434 960192122 481465117 66693499 343818133 632618667 223254725 267807546 609056081 785108597 927583635 230266256 177470214 118310821 505697767 264179196 637512985 368660620 67502152 986755266 385753169 283688064 317247457 771621223 910363228 422278233 975077631 689894201 182565960 186781940 355140500 817558981 260688138 550646708 467506103 622363487 780808186 778903292 905741858 974136221 220054357 944373942 673660083 1222620 361171130 49157839 122322667 966379962 86345646 649218488 176457330 292728730 620143640 250993895 637629841 323987747 234890437 832685396 27296694 113429441 961858533 122861052 681113076 429343011 178187148 232843874 903833984 114571707 306520626 475100425 979128885 718136129 925873971 682348539 484075281 95082289 172989264 775241029 863790774 913104712 847746349 820483960 658142186 643758090 577721809 6532138 927531031 834531135 534229289 251090547 646786507 465193074 974371972 52834161 835556665 922307953 867651864 580384964 924900535 416551632 484294780 375484690 488928062 59017318 936423724 712418436 823549166 24637901 560911625 58756423 580709255 289495782 690292694 174567949 361082096 166582867 654242748 410401417 580643763 240576508 99563462 433206775 325089151 145497483 252656742 863667089 777995173 141372655 605877230 689919771 275373980 835375837 254727960 194672472 802815358 220680522 252011903 439603346 746399880 307972082 631541796 217889046 630349214 165845717 756151786 415495605 619488196 198338228 239835161 869679685 369840806 324154776 743355103 427534878 500018961 314250060 767132106 173758622 12393848 241604574 523185231 62880165 698393712 446103074 327867463 542384154 515353908 870917679 665397868 367520868 205031457 369124320 992650977 742609137 65859387 225650515 43173287 626046130 284033191 588316526 758233385 85067677 162238255 534132821 522245297 758022442 400611009 743552501 707631856 938945751 690647792 114527357 403832954 265168036 371139441 994771679 436203591 412024728 497322656 489040724 691541044 603879482 901660665 684904405 32464256 407012120 553107103 820262562 905058127 29116228 977685464 370011327 806931755 525159633 94919566 962605682 584090494 56839515 743832784 590465991 546804248 986206332 321687119 253113612 265881263 658526808 202088673 72259413 227924314 483370002 379830274 459631353 234902294 657926228 150587982 435781139 207984705 109285836 79030280 633679106 799799074 95884201 599815063 47815913 925550175 971510306 250215939 214341168 534137220 496815855 184530300 713902849 2589571 471427534 81060820 462515659 57048879 185871615 572097280 455962051 415354304 506593225 664514970 172315998 157948242 880549619 890211682 843109081 100108645 900584779 33284536 290978481 629562206 305667107 933347364 650512939 15892741 247202766 297848015 236441549 83494662 242841128 313132295 99084771 254375792 552307468 993372095 60695803 74293816 292186843 81505292 460509801 991796663 235556091 992525225 23631044 505248552 75832918 631777140 779347047 119546667 779808215 46756335 77335537 368004165 645455601 57871808 641046213 355572574 472973335 673662513 293229451 335475265 56639813 214669232 718292653 227556895 835579510 902593104 522879707 729576460 939433515 426784839 358392712 841870721 446071786 953727086 182047594 570917592 502471869 834141892 610866429 828286420 981290415 678207723 389183233 26239510 298974803 342760105 125778680 802937256 605366077 26841705 822135721 582304119 776791174 652371896 779355552 3733457 175556172 369189832 8786347 250232555 238504751 842134512 216057694 646198109 350057686 656677417 570254736 902172323 790839400 533456787 93480156 951025054 464954644 942759150 285409313 140071697 571347593 760239906 714556163 645887526 653074814 959954871 736691303 678825190 583347755 705637213 763257083 629815492 906220238 566008934 146280364 498075923 282757672 345522503 709536301 578218891 727390205 193155867 580476279 573756616 772065688 253638687 854006339 981055179 234748484 688503863 124412306 585598327 447994324 432296296 454580006 846585621 165389596 565039708 327604230 307134673 334137461 298302177 7374590 799089466 585541693 784919146 988249372 671277766 76442453 596371596 689675316 223940683 751629217 826692482 991363933 459352967 46795916 575180458 496411506 731923866 848379777 755595526 356038547 461444487 649457267 769901500 286430625 915262134 377742422 643628183 912552133 826630005 517226403 974302339 361639913 845328242 755744984 367962132 67122749 878210115 682783478 661627904 294238132 947636190 206225921 488732064 197933444 182419745 584693124 226111860 949581482 672452171 631197962 136842140 178220132 379823489 111353510 689685087 835728565 925347146 395529580 838787752 351294692 113514772 839124469 82776708 183350269 978528685 784029407 28986789 781396302 238846410 560967499 832775650 182016747 732645507 794740574 866239413 698810412 441829845 996722368 179872955 481580074 809512735 564363040 947267640 53526597 528020389 361899181 53268880 126467744 906415376 259823262 439056591 138670243 699789804 436951468 359681314 312397177 413701673 17838739 479288668 764700304 853607323 706693269 761301106 425281051 831496826 512818678 572151295 781420947 652677603 235575937 862879425 732870706 537668692 825326593 30035226 910548342 250520116 243489993 233131408 661618596 695398473 5551661 230580557 352368195 438914112 20425991 19503263 196238493 201682216 144719923 844760441 777905729 415749111 252494610 667078129 104248196 672098820 268439051 199843008 584109051 542783883 937866502 151473605 536530178 686757420 511194607 600296578 397113400 809498477 650582841
